package container

type Map[K comparable, V comparable] struct {
	keyToIdx map[K]int
	keys     []K
	values   []V
}

func NewMap[K comparable, K2 comparable]() *Map[K, K2] {
	return &Map[K, K2]{keyToIdx: map[K]int{}, keys: make([]K, 0, 4), values: make([]K2, 0)}
}

func (s *Map[K, V]) Keys() []K {
	return s.keys
}

func (s *Map[K, V]) Values() []V {
	return s.values
}

func (s *Map[K, V]) Get(key K) (V, bool) {
	index, ok := s.keyToIdx[key]
	if !ok {
		return *new(V), false
	}
	return s.values[index], true
}

func (s *Map[K, V]) Cnt() int {
	return len(s.keys)
}

func (s *Map[K, V]) Add(key K, value V) bool {
	_, ex := s.keyToIdx[key]
	if ex {
		return false
	}
	curLen := len(s.keys)
	s.checkSize(curLen + 1)
	s.keyToIdx[key] = curLen
	s.keys = append(s.keys, key)
	s.values = append(s.values, value)
	return true
}

func (s *Map[K, V]) Remove(key K) bool {
	idx, ok := s.keyToIdx[key]
	if !ok {
		return false
	}
	delete(s.keyToIdx, key)
	curLen := len(s.keys)

	//
	tailValue := s.keys[curLen-1]
	s.keys[idx] = tailValue
	s.keyToIdx[tailValue] = idx
	s.keys = s.keys[0 : curLen-1]
	//
	tailValue2 := s.values[curLen-1]
	s.values[idx] = tailValue2
	s.values = s.values[0 : curLen-1]
	//
	s.checkSize(len(s.keys))
	return true
}

func (s *Map[K, V]) checkSize(minSize int) {
	caps := cap(s.keys)
	if caps < minSize*2 && caps > minSize {
		return
	}
	minAllocateSize := s.minAllocSize(minSize)
	//
	newcap := make([]K, minAllocateSize)
	copy(newcap, s.keys)
	s.keys = newcap[0:len(s.keys)]
	//
	newcap2 := make([]V, minAllocateSize)
	copy(newcap2, s.values)
	s.values = newcap2[0:len(s.values)]
}

func (s *Map[K, V]) minAllocSize(x int) int {
	x -= 1
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	//最后再加1返回
	return x + 1
}
